/**
 * @Question.Title: 最长有效括号
 * @Question.No: 32
 * @Author: DQ
 * @Date: 2021-04-20 22:36:39
 * @Description: 
 */
//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 104 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 字符串 动态规划 
// 👍 1277 👎 0

package dq.leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class LongestValidParentheses {
    public static void main(String[] args) {
        Solution solution = new LongestValidParentheses().new Solution();
        String s = "(()())())";
        System.out.println(solution.longestValidParentheses(s));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
        class Solution {
            public int longestValidParentheses(String s) {
                int n = s.length();
                if(n==0) return 0;

                Deque<Integer> stack = new LinkedList<>();
                for(int i = 0; i < s.length(); i++){
                    if(stack.isEmpty() || s.charAt(i)=='(') {
                        stack.push(i);
                        continue;
                    }
                    if(s.charAt(stack.peek()) == '(') stack.pop();
                    else stack.push(i);
                }
                if(stack.isEmpty()) return n;
                int ans = 0;
                int end = n-1, start = 0;
                while(!stack.isEmpty()){
                    start = stack.pop();
                    ans = Math.max(ans, end - start);
                    end = start - 1;
                }
                ans = Math.max(ans, end+1);
                return ans;
            }
            public boolean match(String s, int i, int j){
                return s.charAt(i)=='(' && s.charAt(j) == ')';
            }
        }
//leetcode submit region end(Prohibit modification and deletion)

}